In this video, segment tree is introduced with an example problem.
Codes:
- Method 2(Prefix Sum)
- Method 1(Simple)
This track of the course covers the topic "Segment Trees".
In details, this track will cover:
Objective: The objective of this track is to familiarize the learners with Segment Trees.
Track Content:
Assessment: All Tracks in every week are associated with weekly contests.
In this video, segment tree is introduced with an example problem.
Codes:
In this video segment tree construction is discussed with detailed algorithm.
Codes:
In this video, getSum() query for given array is discussed.
Codes:
In this video update query is discussed with implementation.
Codes:
Can we optimize the time complexity of the first operation in the above solution?
What if the number of query and updates are equal? Can we perform both the operations in O(log n) time once given the array?

Array representation of segment tree for input array {1, 3, 5, 7, 9, 11} is,
st[] = {36, 9, 27, 4, 5, 16, 11, 1, 3, DUMMY, DUMMY, 7, 9, DUMMY, DUMMY}
Query for Sum of given range
Following is the algorithm to get the sum of elements.int getSum(node, l, r)
{
if the range of the node is within l and r
return value in the node
else if the range of the node is completely outside l and r
return 0
else
return getSum(node's left child, l, r) +
getSum(node's right child, l, r)
}
Updating a value
Like tree construction and query operations, the update can also be done recursively. We are given an index which needs to be updated. Let diff be the value to be added. We start from the root of the segment tree and add diff to all nodes which have given index in their range. If a node doesn’t have given index in its range, we don’t make any changes to that node.
// C++ program to show segment tree operations like construction, query
// and update
#include <bits/stdc++.h>
using namespace std;
// A utility function to get the middle index from corner indexes.
int getMid(int s, int e) { return s + (e -s)/2; }
/* A recursive function to get the sum of values in given range
of the array. The following are parameters for this function.
st --> Pointer to segment tree
si --> Index of current node in the segment tree. Initially
0 is passed as root is always at index 0
ss & se --> Starting and ending indexes of the segment represented
by current node, i.e., st[si]
qs & qe --> Starting and ending indexes of query range */
int getSumUtil(int *st, int ss, int se, int qs, int qe, int si)
{
// If segment of this node is a part of given range, then return
// the sum of the segment
if (qs <= ss && qe >= se)
return st[si];
// If segment of this node is outside the given range
if (se < qs || ss > qe)
return 0;
// If a part of this segment overlaps with the given range
int mid = getMid(ss, se);
return getSumUtil(st, ss, mid, qs, qe, 2*si+1) +
getSumUtil(st, mid+1, se, qs, qe, 2*si+2);
}
/* A recursive function to update the nodes which have the given
index in their range. The following are parameters
st, si, ss and se are same as getSumUtil()
i --> index of the element to be updated. This index is
in the input array.
diff --> Value to be added to all nodes which have i in range */
void updateValueUtil(int *st, int ss, int se, int i, int diff, int si)
{
// Base Case: If the input index lies outside the range of
// this segment
if (i < ss || i > se)
return;
// If the input index is in range of this node, then update
// the value of the node and its children
st[si] = st[si] + diff;
if (se != ss)
{
int mid = getMid(ss, se);
updateValueUtil(st, ss, mid, i, diff, 2*si + 1);
updateValueUtil(st, mid+1, se, i, diff, 2*si + 2);
}
}
// The function to update a value in input array and segment tree.
// It uses updateValueUtil() to update the value in segment tree
void updateValue(int arr[], int *st, int n, int i, int new_val)
{
// Check for erroneous input index
if (i < 0 || i > n-1)
{
cout<<"Invalid Input";
return;
}
// Get the difference between new value and old value
int diff = new_val - arr[i];
// Update the value in array
arr[i] = new_val;
// Update the values of nodes in segment tree
updateValueUtil(st, 0, n-1, i, diff, 0);
}
// Return sum of elements in range from index qs (quey start)
// to qe (query end). It mainly uses getSumUtil()
int getSum(int *st, int n, int qs, int qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n-1 || qs > qe)
{
cout<<"Invalid Input";
return -1;
}
return getSumUtil(st, 0, n-1, qs, qe, 0);
}
// A recursive function that constructs Segment Tree for array[ss..se].
// si is index of current node in segment tree st
int constructSTUtil(int arr[], int ss, int se, int *st, int si)
{
// If there is one element in array, store it in current node of
// segment tree and return
if (ss == se)
{
st[si] = arr[ss];
return arr[ss];
}
// If there are more than one elements, then recur for left and
// right subtrees and store the sum of values in this node
int mid = getMid(ss, se);
st[si] = constructSTUtil(arr, ss, mid, st, si*2+1) +
constructSTUtil(arr, mid+1, se, st, si*2+2);
return st[si];
}
/* Function to construct segment tree from given array. This function
allocates memory for segment tree and calls constructSTUtil() to
fill the allocated memory */
int *constructST(int arr[], int n)
{
// Allocate memory for the segment tree
//Height of segment tree
int x = (int)(ceil(log2(n)));
//Maximum size of segment tree
int max_size = 2*(int)pow(2, x) - 1;
// Allocate memory
int *st = new int[max_size];
// Fill the allocated memory st
constructSTUtil(arr, 0, n-1, st, 0);
// Return the constructed segment tree
return st;
}
// Driver program to test above functions
int main()
{
int arr[] = {1, 3, 5, 7, 9, 11};
int n = sizeof(arr)/sizeof(arr[0]);
// Build segment tree from given array
int *st = constructST(arr, n);
// Print sum of values in array from index 1 to 3
cout<<"Sum of values in given range = "<<getSum(st, n, 1, 3)<<endl;
// Update: set arr[1] = 10 and update corresponding
// segment tree nodes
updateValue(arr, st, n, 1, 10);
// Find sum after the value is updated
cout<<"Updated sum of values in given range = "
<<getSum(st, n, 1, 3)<<endl;
return 0;
}
// Java Program to show segment tree operations like construction,
// query and update
class SegmentTree
{
int st[]; // The array that stores segment tree nodes
/* Constructor to construct segment tree from given array. This
constructor allocates memory for segment tree and calls
constructSTUtil() to fill the allocated memory */
SegmentTree(int arr[], int n)
{
// Allocate memory for segment tree
//Height of segment tree
int x = (int) (Math.ceil(Math.log(n) / Math.log(2)));
//Maximum size of segment tree
int max_size = 2 * (int) Math.pow(2, x) - 1;
st = new int[max_size]; // Memory allocation
constructSTUtil(arr, 0, n - 1, 0);
}
// A utility function to get the middle index from corner indexes.
int getMid(int s, int e) {
return s + (e - s) / 2;
}
/* A recursive function to get the sum of values in given range
of the array. The following are parameters for this function.
st --> Pointer to segment tree
si --> Index of current node in the segment tree. Initially
0 is passed as root is always at index 0
ss & se --> Starting and ending indexes of the segment represented
by current node, i.e., st[si]
qs & qe --> Starting and ending indexes of query range */
int getSumUtil(int ss, int se, int qs, int qe, int si)
{
// If segment of this node is a part of given range, then return
// the sum of the segment
if (qs <= ss && qe >= se)
return st[si];
// If segment of this node is outside the given range
if (se < qs || ss > qe)
return 0;
// If a part of this segment overlaps with the given range
int mid = getMid(ss, se);
return getSumUtil(ss, mid, qs, qe, 2 * si + 1) +
getSumUtil(mid + 1, se, qs, qe, 2 * si + 2);
}
/* A recursive function to update the nodes which have the given
index in their range. The following are parameters
st, si, ss and se are same as getSumUtil()
i --> index of the element to be updated. This index is in
input array.
diff --> Value to be added to all nodes which have i in range */
void updateValueUtil(int ss, int se, int i, int diff, int si)
{
// Base Case: If the input index lies outside the range of
// this segment
if (i < ss || i > se)
return;
// If the input index is in range of this node, then update the
// value of the node and its children
st[si] = st[si] + diff;
if (se != ss) {
int mid = getMid(ss, se);
updateValueUtil(ss, mid, i, diff, 2 * si + 1);
updateValueUtil(mid + 1, se, i, diff, 2 * si + 2);
}
}
// The function to update a value in input array and segment tree.
// It uses updateValueUtil() to update the value in segment tree
void updateValue(int arr[], int n, int i, int new_val)
{
// Check for erroneous input index
if (i < 0 || i > n - 1) {
System.out.println("Invalid Input");
return;
}
// Get the difference between new value and old value
int diff = new_val - arr[i];
// Update the value in array
arr[i] = new_val;
// Update the values of nodes in segment tree
updateValueUtil(0, n - 1, i, diff, 0);
}
// Return sum of elements in range from index qs (quey start) to
// qe (query end). It mainly uses getSumUtil()
int getSum(int n, int qs, int qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n - 1 || qs > qe) {
System.out.println("Invalid Input");
return -1;
}
return getSumUtil(0, n - 1, qs, qe, 0);
}
// A recursive function that constructs Segment Tree for array[ss..se].
// si is index of current node in segment tree st
int constructSTUtil(int arr[], int ss, int se, int si)
{
// If there is one element in array, store it in current node of
// segment tree and return
if (ss == se) {
st[si] = arr[ss];
return arr[ss];
}
// If there are more than one elements, then recur for left and
// right subtrees and store the sum of values in this node
int mid = getMid(ss, se);
st[si] = constructSTUtil(arr, ss, mid, si * 2 + 1) +
constructSTUtil(arr, mid + 1, se, si * 2 + 2);
return st[si];
}
// Driver program to test above functions
public static void main(String args[])
{
int arr[] = {1, 3, 5, 7, 9, 11};
int n = arr.length;
SegmentTree tree = new SegmentTree(arr, n);
// Build segment tree from given array
// Print sum of values in array from index 1 to 3
System.out.println("Sum of values in given range = " +
tree.getSum(n, 1, 3));
// Update: set arr[1] = 10 and update corresponding segment
// tree nodes
tree.updateValue(arr, n, 1, 10);
// Find sum after the value is updated
System.out.println("Updated sum of values in given range = " +
tree.getSum(n, 1, 3));
}
}
Sum of values in given range = 15
Updated sum of values in given range = 22

// qs --> query start index, qe --> query end index
int RMQ(node, qs, qe)
{
if the range of node is within qs and qe
return value in the node
else if the range of node is completely outside qs and qe
return INFINITE
else
return min( RMQ(node's left child, qs, qe),
RMQ(node's right child, qs, qe) )
}
// C++ program for range minimum
// query using segment tree
#include <bits/stdc++.h>
using namespace std;
// A utility function to get minimum of two numbers
int minVal(int x, int y) { return (x < y)? x: y; }
// A utility function to get the
// middle index from corner indexes.
int getMid(int s, int e) { return s + (e -s)/2; }
/* A recursive function to get the
minimum value in a given range
of array indexes. The following
are parameters for this function.
st --> Pointer to segment tree
index --> Index of current node in the
segment tree. Initially 0 is
passed as root is always at index 0
ss & se --> Starting and ending indexes
of the segment represented
by current node, i.e., st[index]
qs & qe --> Starting and ending indexes of query range */
int RMQUtil(int *st, int ss, int se, int qs, int qe, int index)
{
// If segment of this node is a part
// of given range, then return
// the min of the segment
if (qs <= ss && qe >= se)
return st[index];
// If segment of this node
// is outside the given range
if (se < qs || ss > qe)
return INT_MAX;
// If a part of this segment
// overlaps with the given range
int mid = getMid(ss, se);
return minVal(RMQUtil(st, ss, mid, qs, qe, 2*index+1),
RMQUtil(st, mid+1, se, qs, qe, 2*index+2));
}
// Return minimum of elements in range
// from index qs (quey start) to
// qe (query end). It mainly uses RMQUtil()
int RMQ(int *st, int n, int qs, int qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n-1 || qs > qe)
{
cout<<"Invalid Input";
return -1;
}
return RMQUtil(st, 0, n-1, qs, qe, 0);
}
// A recursive function that constructs
// Segment Tree for array[ss..se].
// si is index of current node in segment tree st
int constructSTUtil(int arr[], int ss, int se,
int *st, int si)
{
// If there is one element in array,
// store it in current node of
// segment tree and return
if (ss == se)
{
st[si] = arr[ss];
return arr[ss];
}
// If there are more than one elements,
// then recur for left and right subtrees
// and store the minimum of two values in this node
int mid = getMid(ss, se);
st[si] = minVal(constructSTUtil(arr, ss, mid, st, si*2+1),
constructSTUtil(arr, mid+1, se, st, si*2+2));
return st[si];
}
/* Function to construct segment tree
from given array. This function allocates
memory for segment tree and calls constructSTUtil() to
fill the allocated memory */
int *constructST(int arr[], int n)
{
// Allocate memory for segment tree
//Height of segment tree
int x = (int)(ceil(log2(n)));
// Maximum size of segment tree
int max_size = 2*(int)pow(2, x) - 1;
int *st = new int[max_size];
// Fill the allocated memory st
constructSTUtil(arr, 0, n-1, st, 0);
// Return the constructed segment tree
return st;
}
// Driver Code
int main()
{
int arr[] = {1, 3, 2, 7, 9, 11};
int n = sizeof(arr)/sizeof(arr[0]);
// Build segment tree from given array
int *st = constructST(arr, n);
int qs = 1; // Starting index of query range
int qe = 5; // Ending index of query range
// Print minimum value in arr[qs..qe]
cout<<"Minimum of values in range ["<<qs<<", "<<qe<<"] "<<
"is = "<<RMQ(st, n, qs, qe)<<endl;
return 0;
}
// Program for range minimum query using segment tree
class SegmentTreeRMQ
{
int st[]; //array to store segment tree
// A utility function to get minimum of two numbers
int minVal(int x, int y) {
return (x < y) ? x : y;
}
// A utility function to get the middle index from corner
// indexes.
int getMid(int s, int e) {
return s + (e - s) / 2;
}
/* A recursive function to get the minimum value in a given
range of array indexes. The following are parameters for
this function.
st --> Pointer to segment tree
index --> Index of current node in the segment tree. Initially
0 is passed as root is always at index 0
ss & se --> Starting and ending indexes of the segment
represented by current node, i.e., st[index]
qs & qe --> Starting and ending indexes of query range */
int RMQUtil(int ss, int se, int qs, int qe, int index)
{
// If segment of this node is a part of given range, then
// return the min of the segment
if (qs <= ss && qe >= se)
return st[index];
// If segment of this node is outside the given range
if (se < qs || ss > qe)
return Integer.MAX_VALUE;
// If a part of this segment overlaps with the given range
int mid = getMid(ss, se);
return minVal(RMQUtil(ss, mid, qs, qe, 2 * index + 1),
RMQUtil(mid + 1, se, qs, qe, 2 * index + 2));
}
// Return minimum of elements in range from index qs (quey
// start) to qe (query end). It mainly uses RMQUtil()
int RMQ(int n, int qs, int qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n - 1 || qs > qe) {
System.out.println("Invalid Input");
return -1;
}
return RMQUtil(0, n - 1, qs, qe, 0);
}
// A recursive function that constructs Segment Tree for
// array[ss..se]. si is index of current node in segment tree st
int constructSTUtil(int arr[], int ss, int se, int si)
{
// If there is one element in array, store it in current
// node of segment tree and return
if (ss == se) {
st[si] = arr[ss];
return arr[ss];
}
// If there are more than one elements, then recur for left and
// right subtrees and store the minimum of two values in this node
int mid = getMid(ss, se);
st[si] = minVal(constructSTUtil(arr, ss, mid, si * 2 + 1),
constructSTUtil(arr, mid + 1, se, si * 2 + 2));
return st[si];
}
/* Function to construct segment tree from given array. This function
allocates memory for segment tree and calls constructSTUtil() to
fill the allocated memory */
void constructST(int arr[], int n)
{
// Allocate memory for segment tree
//Height of segment tree
int x = (int) (Math.ceil(Math.log(n) / Math.log(2)));
// Maximum size of segment tree
int max_size = 2 * (int) Math.pow(2, x) - 1;
st = new int[max_size]; // allocate memory
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, 0);
}
// Driver Code
public static void main(String args[])
{
int arr[] = {1, 3, 2, 7, 9, 11};
int n = arr.length;
SegmentTreeRMQ tree = new SegmentTreeRMQ();
// Build segment tree from given array
tree.constructST(arr, n);
int qs = 1; // Starting index of query range
int qe = 5; // Ending index of query range
// Print minimum value in arr[qs..qe]
System.out.println("Minimum of values in range [" + qs + ", "
+ qe + "] is = " + tree.RMQ(n, qs, qe));
}
}
Minimum of values in range [1, 5] is = 2